package leetcode_core.leetcode_1;

import java.util.HashMap;

public class LRU {
    //key->leetocde_1.Node(key,val)
    private HashMap<Integer, Node> map;
    //leetocde_1.Node(k1,v1)<->leetocde_1.Node(k2,v2)
    private DoubleList cache;
    //最大容量
    private int cap;
    public LRU(int cap){
        this.cap = cap;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    /*将某个key提升为最近使用*/
    private void makeRecently(int key){
        Node x= map.get(key);
        //先从链表中删除该节点
        cache.remove(x);
        //将该节点插入到表尾
        cache.addList(x);
    }

    /**
     * 添加最近使用的元素
     * @param key
     * @param val
     */
    private void addRecently(int key,int val){
        Node x = new Node(key,val);
        //链表尾部就是最近使用的元素
        cache.addList(x);
        //别忘了在map中添加key的映射
        map.put(key,x);
    }

    /**
     * 删除某一个key
     * @param key
     */
    private void deleteKey(int key){
        Node x = map.get(key);
        //从链表中删除该key所对应的节点
        cache.remove(x);
        //从map中删除
        map.remove(x);
    }

    /**
     * 删除最久没有使用的元素
     */
    private void removeLeastRecently(){
        //链表头部的第一个元素就是最久未使用的
        Node deleteNode = cache.removeFirstNode();
        //同时从map中删除它的key
        int key = deleteNode.key;
        map.remove(key);
    }

    /**
     * 外部取cache的值
     * @param key
     * @return
     */
    public int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }
        //将该数据提升为最近使用的
        makeRecently(key);
        return map.get(key).val;
    }

    /**
     *
     * @param key
     * @param val
     */
    public void put(int key,int val){
        if(map.containsKey(key)){
            //如果有相同的key值,那么就删除旧的数据
            deleteKey(key);
            //新插入的数据为最近使用的数据
            this.addRecently(key,val);
            return;
        }
        //如果是新的数据,那么就需要淘汰一页后插入
        if(cap == cache.getSize()){
            //删除最久未使用的元素
            removeLeastRecently();
        }
        //添加最近使用的元素
        addRecently(key, val);

    }



}

//定义双链表的节点类,注意双链表的话是需要有两个指针,一个指针指向前面,一个指针指向后面
class Node {
    public int key;
    public int val;
    public Node next,prev;
    public Node(int k,int v){
        this.key=k;
        this.val=v;
    }
}
//依靠Node类型构建双链表
class DoubleList{
    //头尾的虚节点
    private Node head,tail;
    //链表的元素个数
    private int size;

    public DoubleList(){
        //初始化双向链表的数据
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next=tail;
        //头结点没有上一个节点,下一个节点是尾结点
        tail.prev=head;
        //尾结点有上一个节点,没有下一个节点
        this.size = 0;
    }

    //在链表尾部添加节点x,时间复杂度为O(1)
    public void addList(Node x){
        //修改指针
        //x节点的上一个节点设置为tail的上一个节点
        x.prev = tail.prev;
        //x节点的下一个节点设置为tail
        x.next = tail;
        //tail节点的上一个节点的下一个节点属性设置为x
        tail.prev.next = x;
        //tail节点的上一个节点设置为x
        tail.prev =x;
        //链表长度+1
        this.size++;
    }

    //删除链表中的x节点(x一定存在)
    //由于是双链表而且给的是目标Node节点,时间复杂度是O(1)
    public void remove(Node x){
        //先处理之前节点的关系
        //使得x的上一个节点连接x的下一个节点
        x.prev.next = x.next;
        //使得x的下一个节点连接x的上一个节点
        x.next.prev = x.prev;
        this.size--;
    }

    //删除链表中的第一个节点,并返回该节点,时间复杂度为O(1)
    public Node removeFirstNode(){
        if(head.next == tail){
            return null;
        }
        Node x = head.next;
        //头节点的下一个节点指向第一个节点的下一个节点
        head.next = x.next;
        //第一个节点的下一个节点的上一个节点属性指向头结点
        x.next.prev = head;
        this.size--;
        return x;
    }

    //获取链表总长度
    public int getSize(){
        return this.size;
    }

}
